using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace AntsMap
{
    class SolverACO : Solver
    {
        private SolutionPermuter solgen;
        private Ant[] antcolony;
        private PheroMap phero1;
        private PheroMap phero2;

        private string message; //string we can set and print out in Message()
       
        private int bestindex;
        private bool intensify;
        private Random random;
        private int noimprovecount;
        // parameters from HAS-QAP
        private int m;  //number of ants in HAS QAP
        private double Q;
        private double R;
        private double S;
        private double q;

        // --------------------------------------------------------------------------------------
        //
        // --------------------------------------------------------------------------------------
        public SolverACO(int[,] soln, int dim, int elem, CostMap map, int ants )
        {
            // Make new arrays and give them the values of soln
            solution = new int[elem,dim];
            Array.Copy(soln, solution, elem * dim);
            prevsol = new int[elem, dim];
            Array.Copy(soln, prevsol, elem * dim);
            bestsol = new int[elem, dim];
            Array.Copy(soln, bestsol, elem * dim);

            bestcost = 1000000000; //TODO fix hardcode
            dimensions = dim;
            elements = elem;
            costmap = map;
            random = new Random();
            Optimal = false;
            curiter = 0;
            maxiter = 100; // HAS-QAP uses 10 and 100 commonly


            noimprovecount = 0; // iterations without improving the global best solution
            solgen = new SolutionPermuter(map.Elements, map.Dimension);
            // An array of ants who will work this problem
            antcolony = new Ant[ ants ];

            // Pheromone maps (2 for the 3DAP)
            phero1 = new PheroMap(elem, 0);
            phero2 = new PheroMap(elem, 1);

            // Create #ants initial solutions, one for each ant
            // Run each solution through local optimization to improve it
            for (int i = 0; i < ants; i++)
            {
                antcolony[i] = new Ant(elements, dimensions);
                antcolony[i].pisol = OptimizeWithLocalSearch(solgen.GenerateSolution());
                antcolony[i].DuplicateInitial(); // set the other solutions to pisol, as we will modify it as we go
            }

            // initialize parameters for algorithm
            //alpha1 = alpha2 = 0.1;  <-- see PheroMap.cs for these (alpha-2 and evaprate)
            Q = 100;
            R = elements / 3;
            S = elements / 2;
            q = 0.9;

            // Get the index of the ant with the best solution
            bestindex = IndexOfBest(antcolony, costmap);
            // Get the solution from that ant
            //bestsol = antcolony[bestindex].pisol;
            Array.Copy(antcolony[bestindex].pisol, bestsol, elem * dim);
            // Calculate the optimal cost so far based on that solution
            int optcost = costmap.Cost(bestsol);
            
            // Based on the best solution so far initialize the pheromone maps to
            // a default intensity.
            double level = 1 / (Q * optcost);
            phero1.Initialize( level );
            phero2.Initialize( level );
            
            // activate intensification
            intensify = true; 
        }

        // --------------------------------------------------------------------------------------
        // Get the index of the current lowest-cost solution
        // --------------------------------------------------------------------------------------
        private int IndexOfBest(Ant[] sols, CostMap costs)
        {
            int lowestcost = 10000000;
            int bestindex = 0;
 
            for (int i = 0; i < sols.Length; i++)
            {
                int curcost = costs.Cost(sols[i].pisol);
                if (curcost < lowestcost)
                {
                    bestindex = i;
                    lowestcost = curcost;
                }
            }
            return bestindex;
        }


        // --------------------------------------------------------------------------------------
        // Use this to make the initial solutions 
        // a little better.  For use before starting the algorithm.
        // NOTE - will modify the array passed in permanently
        // --------------------------------------------------------------------------------------
        private int[,] OptimizeWithLocalSearch(int[,] solution)
        {
            int bestcost = 10000000; //todo fix
            int[,] prevsoln = solution;


            // The column we're in
            for (int i = 0; i < dimensions; i++)
            {
                // The main index to permute with in the column
                for (int j = 0; j < elements - 1; j++)
                {
                    // The indices to continually swap with, down the column
                    for (int k = j + 1; k < elements; k++)
                    {
                        int tval = solution[j, i];
                        solution[j, i] = solution[k, i];
                        solution[k, i] = tval;

                        if (costmap.Cost(solution) < bestcost)
                        {
                            // improvement found; copy into prevsol
                            bestcost = costmap.Cost(solution);
                            Array.Copy(solution, prevsol, elements * dimensions);
                        }
                        else
                        {
                            // didn't improve, go back a step (restore prevsol)
                            Array.Copy(prevsol, solution, elements * dimensions);
                        }

                    }
                }
            }
            return solution;
        }

        // --------------------------------------------------------------------------------------
        //
        // --------------------------------------------------------------------------------------
        public override int[,] SolveStep()
        {
            int row = 0;
            int col = 0;
            bool improved = false; // gets set to true if an ant, in this step, improves its soln

            // for each ant, do the following I-max times (each call to SolveStep is one iteration of Imax)
            // pheromone swap stage
            for (int i = 0; i < antcolony.Length; i++)
            {
                // Perform R pheromone trail swaps to obtain pihat
                for (int swaps = 0; swaps < R; swaps++)
                {
                    // Pick row to select the indexes to swap from
                    int rowindex1 = random.Next(0, this.elements);  // a random index into the rows
                    // Now get other rows to flip with, based on some methods below
                    int rowindex2 = 0;  // this is the flip index in the first dimension
                    int rowindex3 = 0;  // this is the flip that occurs in the *second* dimension

                    double whichway = random.NextDouble();
                    //this.q = 0.0;
                    if (whichway <= q)
                    {
                        // EXPLOIT - maximize sum of index1 and s pheromones

                        // Look at the row we picked and the zeroth and first columns
                        // to get the coordinates of the corresponding pheromone entry for
                        // that particular linkage.
                        // eg,
                        //   0 2 2  <--- picking this means first element (0th) is linked to 2nd in next column 
                        //   1 0 1         so go to (0,2) in ExE pheromone matrix to see strenght of that link
                        //   ...
                        row = antcolony[i].pisol[rowindex1,0];
                        col = antcolony[i].pisol[rowindex1,1];
                        rowindex2 = phero1.IndexByPolicyMaximizeSum(row, col, antcolony[i].pisol, this.elements);
                        
                        // we can do this since we know there are 3 (and only 3) columns
                        row = antcolony[i].pisol[rowindex1,1];
                        col = antcolony[i].pisol[rowindex1,2];
                        rowindex3 = phero2.IndexByPolicyMaximizeSum(row, col, antcolony[i].pisol, this.elements);
                    }
                    else
                    {
                        // EXPLORE - choose it probabilistically (10% of the time by HAS-QAP)
                        row = antcolony[i].pisol[rowindex1, 0];
                        col = antcolony[i].pisol[rowindex1, 1];
                        rowindex2 = phero1.IndexByPolicyProbability(row, col, antcolony[i].pisol, this.elements);

                        // we can do this since we know there are 3 (and only 3) columns
                        row = antcolony[i].pisol[rowindex1, 1];
                        col = antcolony[i].pisol[rowindex1, 2];
                        rowindex3 = phero2.IndexByPolicyProbability(row, col, antcolony[i].pisol, this.elements);
                    }

                    // Perform the swap now that the two row indices are decided - produce pihat from pisol
                    // swap for first column
                    int tval = antcolony[i].pisol[rowindex1, 0];
                    antcolony[i].pisol[rowindex1, 0] = antcolony[i].pisol[rowindex2, 0];
                    antcolony[i].pisol[rowindex2, 0] = tval;
                    // swap for second column
                    tval = antcolony[i].pisol[rowindex1, 1];
                    antcolony[i].pisol[rowindex1, 1] = antcolony[i].pisol[rowindex3, 1];
                    antcolony[i].pisol[rowindex3, 1] = tval;
                    // Now copy the new, swapped pisol into pihat for this ant.  It should change with 
                    // each of our R iterations.
                    Array.Copy(antcolony[i].pisol, antcolony[i].pihat, this.elements * this.dimensions);
                   
                }//end R pheromone swaps
                
                //Apply the local search procedure to pihat to obtain pitilde (this alters permanently pihat)
                Array.Copy(OptimizeWithLocalSearch(antcolony[i].pihat), antcolony[i].pitilde, this.elements * this.dimensions);
                // Now pisol is as it was.  pihat and pitilde are equal (due to local opt reference).
               
            }// end for each ant
               
            //for each ant:
            bool better_sol_found = false;
            for (int i = 0; i < antcolony.Length; i++)
            {
                // if intensification is active, pi(i+1) = best permu between pi(i) and pitilde
                if (intensify == true)
                {
                    // allow for a replacement of pisol by pitilde to occur if pitilde is better
                    if (costmap.Cost(antcolony[i].pisol) > costmap.Cost(antcolony[i].pitilde))
                    {
                        Array.Copy(antcolony[i].pitilde, antcolony[i].pisol, this.elements * this.dimensions);
                        better_sol_found = true;
                    }
                    // else pisol remains for the next iteration
                }
                else
                {
                    // pi(i+1) = pitilde, next is same as now
                    continue;
                }
            }
            // If no ant was able to better his solution while intensification active, then deactivate
            if (better_sol_found == false)
            {
                this.intensify = false;
                this.message += "INTENSIFY DEactivated\n";
            }
            bool improvement_made = false;
            // if there exists a pitilde cost that is < bestcost, update bestcost, bestsol and activate intensification
            for (int i = 0; i < antcolony.Length; i++)
            {
                if (costmap.Cost(antcolony[i].pitilde) < this.bestcost)
                {
                    this.bestcost = costmap.Cost(antcolony[i].pitilde);
                    Array.Copy(antcolony[i].pitilde, this.bestsol, this.elements * this.dimensions);
                    this.intensify = true;
                    improvement_made = true;
                    this.message += "INTENSIFY activated\n";

                }
            }
            if (improvement_made == true)
            {
                this.noimprovecount = 0;
            }
            else
                this.noimprovecount++;

            // Update pheromone matrix now
            phero1.Evaporate();
            phero2.Evaporate();

            phero1.Intensify(this.bestsol, this.bestcost);
            phero2.Intensify(this.bestsol, this.bestcost);
            
            
            // Diversify: if no new best in S iterations, diversify()
            if (this.noimprovecount > this.S)
            {
                phero1.Diversify();
                phero2.Diversify();
                this.message = "DIVERSIFY()\n";
            }
            
            
            // Finish if max iterations is 100 (or 10 for short run)
            if (this.curiter >= this.maxiter)
                this.Optimal = true;

            this.curiter++;

            return bestsol;
        }

       

        // --------------------------------------------------------------------------------------
        //
        // --------------------------------------------------------------------------------------
        public override int[,] BestSolution()
        {
            return bestsol;
        }

        // --------------------------------------------------------------------------------------
        //
        // --------------------------------------------------------------------------------------
        public override int BestCost()
        {
            return bestcost;
        }

        // --------------------------------------------------------------------------------------
        //
        // --------------------------------------------------------------------------------------
        public override string Message()
        {
            return this.message + "curiter is " + this.curiter.ToString() + "\n";
            //return this.phero1.PheroMapAsString() + this.phero2.PheroMapAsString();
        }



    }
}
